1139D - Steps to One - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define int long long int
const int max_n =1e5, mod = 1e9 + 7;

int pw(int a, int b) {
    if (b == 0)
        return 1;
    int k = pw(a, b / 2);
    if (b % 2 == 0)
        return ((k * k) % mod);
    return k * k % mod * a % mod;
}

int dp[max_n + 10], m, ans = 1;

int32_t main() {
    cin >> m;
    for (int i = 2; i <= m; i++){
        int p = (m / i) * pw(m, mod - 2) % mod;
        dp[i] = p * pw((1 - p + mod) % mod, mod - 2) % mod;
    }

    for (int i = m; i >= 2; i--)
        for (int j = 2 * i; j <= m; j += i)
            dp[i] = ((dp[i] - dp[j]) % mod + mod) % mod;
        
    for (int i = 2; i <= m; i++) 
        ans = (ans + dp[i]) % mod;
    
    cout << ans;
}